/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {number[]}
 */
export var getAllElements = function (root1, root2) {
  const getOneElements = (node, elememts = []) => {
    if (node) {
      getOneElements(node.left, elememts)
      elememts.push(node.val)
      getOneElements(node.right, elememts)
    }
  }
  const [ele1, ele2] = [[], []]
  getOneElements(root1, ele1)
  getOneElements(root2, ele2)
  let [i, j] = [0, 0]
  const ans = []
  while (i < ele1.length || j < ele2.length) {
    if (i === ele1.length) {
      ans.push(ele2[j])
      j++
      continue
    }
    if (j === ele2.length) {
      ans.push(ele1[i])
      i++
      continue
    }
    if (ele1[i] < ele2[j]) {
      ans.push(ele1[i++])
    } else {
      ans.push(ele2[j++])
    }
  }
  return ans
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {number[]}
 */
export var getAllElements2 = function (root1, root2) {
  const result = []
  const queue = [root1, root2]
  while (queue.length) {
    const node = queue.shift()
    if (node) {
      result.push(node.val)
      queue.push(node.left, node.right)
    }
  }
  return result.sort((a, b) => a - b)
}
